# -*- coding: utf-8 -*-

"""354. 俄罗斯套娃信封问题
给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
注意：不允许旋转信封。

示例 1：
输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出：3
解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

示例 2：
输入：envelopes = [[1,1],[1,1],[1,1]]
输出：1

提示：
1 <= envelopes.length <= 10^5
envelopes[i].length == 2
1 <= wi, hi <= 10^5"""

from random import randint

class Solution:
    """
    按通常建模来看，需要按偏序关系画图，然后再图上找最大距离就好了。
    不过我们可以改变原始序列，最后转化为找最大递增子序列的问题。
    为什么原始序列不行？比如例1，在计算到元素 [6,7] 的时候，最长子序列距离是2，下一个元素是 [2,3]，这个元素最小，可以套在前面的任何元素中，所以 [6,7] 会更新为3（无后效性？）。
    所以可以先给这个原始无逻辑的序列按递增排序，这就转化为求最大递增子序列的距离了。这个题给出的难度是困难，估计是要实现一个快排吧。
    在写快排的时候，使用了龙书代码优化那节双指针项目靠拢的方法，一直处理不了等于判断的情形。最后发现这个套娃的题可以使用去重的方法。毕竟相同长宽的信封，不论几个，在合适的位置只能使用一个。
    最后看题解，还可以优化，这个序结构，本身就是按升序排列，那么我们可以将二维转化为一维。
    对同样的宽度 w，套信封的时候只能选一个高度 h 的，那么我们可以将每个 w 中的 h 按降序排列，这样走势图就是左陡右缓状，w 本身呈前后序关系，拉通取 h 的最大距离递增子序列就可以了。
    ---------------------------------------------------------
    用动态规划的方法 dp[i] = max(dp[j]+1, dp[i]), j < i 且 h[j] < h[i]；在这个过程中还需要对每个 [0,i) 进行遍历，时间复杂度很高。看题解，还有一种贪心算法。
    考虑这样一种场景，提供一个有序序列，迭代这个序列，一点点地构建偏序图的过程。迭代的先后本身就包含 j < i 的关系，所以当 h[i] 与偏序图中的任意顶点 j 满足 h[j] < h[i] 的关系，都可以将 iRj 这个关系添加到偏序图中。动态规划中，是记录以元素 i 为尾元素的最长增长路径。
    那么在这个偏序图中，都是那些点，距离最大的增长路径，就是增长最缓的路径。那么是否可以找到这条最缓增长路径？
    定义集合 greedy[d] 为偏序图中距离为 d 的增长路径的最小尾元素。对 h[i], 如果集合中存在某个最小的 g[d] 使 g[d] > h[i]，则 g[d] = h[i]，不会有再长一步的路径产生；
                                                                       如果 all(g[d]) < h[i], 则应该有再长一步的路径产生。
    如果将结合 greedy 按距离由小到大排序，则可以证明 g 具有单调性。如果 x < y,  则 g[x] < g[y]。容易证明，在偏序图中，长度为 y 的路径集合，是包含长度为 x 的路径集合，类似子图的关系。
    这个单调性很重要，就能用较快的二分查找，节省很多时间。
    """
    def maxEnvelopesDynamic(self, envelopes: list) -> int:
        envelopes = list(set([(i[0], i[1]) for i in envelopes]))
        self.quikSort(envelopes)
        envelopes = [i[1] for i in envelopes]

        dp = [1 for _ in envelopes]

        i = 0
        while i < len(envelopes):
            j = 0
            while j < i:
                if envelopes[j] < envelopes[i]:
                    dp[i] = max(dp[i], dp[j]+1)
                j += 1
            i += 1
        return max(dp)

    def maxEnvelopes(self, envelopes):
        envelopes = list(set([(i[0], i[1]) for i in envelopes]))
        self.quikSort(envelopes)
        envelopes = [i[1] for i in envelopes]
        g = [0]
        for h in envelopes:
            if g[-1] < h:
                g.append(h)
            elif g[-1] == h:
                continue
            else:
                head, tail = 0, len(g)-1
                while True:
                    middle = (head + tail) // 2
                    if middle == head and g[tail] >= h:
                        g[tail] = h
                        break
                    if g[middle] > h:
                        head, tail = head, middle
                    elif g[middle] < h:
                        head, tail = middle, tail
                    else:
                        head, tail = middle, middle
        return len(g)-1

    @staticmethod
    def quikSort(envelopes):
        """这种使用相互靠拢的方法分区不适合等于判断，适合无重复的元素排序"""
        def do(m, n):
            i, j, x = m, n, envelopes[randint(m,n)]
            while True:
                while i < j and Solution.lt(envelopes[i], x):
                    i += 1
                while i < j and Solution.gt(envelopes[j], x):
                    j -= 1

                if i >= j:
                    pivot = i
                    break
                else:
                    envelopes[i], envelopes[j] = envelopes[j], envelopes[i]

            if pivot-1 > m:
                do(m, pivot-1)
            if n > pivot+1:
                do(pivot+1, n)
        do(0, len(envelopes)-1)

    @staticmethod
    def lt(envelopeA, envelopeB):
        if envelopeA[0] < envelopeB[0]:
            return True
        elif envelopeA[0] == envelopeB[0] and envelopeA[1] > envelopeB[1]:
            return True
        else:
            return False
        
    @staticmethod
    def gt(envelopeA, envelopeB):
        if envelopeA[0] > envelopeB[0]:
            return True
        elif envelopeA[0] == envelopeB[0] and envelopeA[1] < envelopeB[1]:
            return True
        else:
            return False

if __name__ == '__main__':
    rs = Solution().maxEnvelopes([[5,4],[6,4],[6,7],[2,3]])
    print(rs)
